package mo.offer_special;

import java.util.HashMap;
import java.util.Map;

@SuppressWarnings("Duplicates")
public class L065 {

    public int minimumLengthEncoding(String[] words) {
        Trie trie = new Trie();
        Map<Trie, Integer> node2idx = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            Trie cur = trie;
            for (int j = words[i].length()-1; j >= 0; j--) {
                int idx = words[i].charAt(j) - 'a';
                cur = cur.get(idx);
            }
            node2idx.put(cur, i);
        }

        int ret = 0;
        for (Map.Entry<Trie, Integer> entry : node2idx.entrySet()) {
            if (entry.getKey().count == 0) {
                ret += words[entry.getValue()].length() + 1;
            }
        }
        return ret;
    }



    private static class Trie {
        public Trie[] children;
        public int count;

        public Trie() {
            children = new Trie[26];
            count = 0;
        }

        public Trie get(int idx) {
            if (this.children[idx] == null) {
                this.children[idx] = new Trie();
                this.count++;
            }
            return this.children[idx];
        }
    }

    public static void main(String[] args) {
        L065 test = new L065();
        System.out.println(test.minimumLengthEncoding(new String[]{"time", "me", "bell"}));



    }

}
